2.1 高斯消去法

本文内容由简易程序从latex批量转义而来, 排版并不友好, 相对精美版请见课程整理

高斯消去法

本质上就是初等数学中的消元法, 但是规范了求解步骤, 便于编写计算机程序.

基本思路就是先将矩阵消元成上三角矩阵, 再根据最后一行的解依次回代.

乘除运算量: 消元部分 \(N_1=\sum\limits_{k=1}^{n-1}[(n-k)^2+2(n-k)]=\dfrac{n^3}{3}+\dfrac{n^2}{2}-\dfrac{5n}{6}\), 回代部分 \(N_2=\sum\limits_{k=1}^{n-1}(n-k)=\dfrac{n^2}{2}+\dfrac{n}{2}\), 总共为 \(N=\dfrac{1}{3}n^3+n^2-\dfrac 1 3 n\).

使用条件: 要求系数矩阵的秩等于 \(n\), 即解唯一, 也就是顺序主子式均不为 \(0\).

列主元法

在上述消元过程中可能会遇到主元 \(a_{k,k}^{(k-1)}=0\), 或者 \(|a_{k,k}^{(k-1)}|\) 很小, 那么如果我们以这样的主元进行计算就会导致数量级的剧增 (因为涉及除法)和舍入误差的增长.

为了避免上述问题, 我们在每次选取主元时, 应选择该列绝对值最大的那一行并将其交换至第 \(k\) 行再进行消元.

在列主元法中 \(|a_{i,k}^{(k-1)}|/|a_{k,k}^{(k-1)}|\leqslant 1\), 这就有利于控制误差的传播, 有较好的数值稳定性.